package com.cyy.test_t_6_;

/**
 * @Description 剑指Offer t_61 - 序列化二叉树
 * 题目描述：
 * 请实现两个函数，分别用来序列化和反序列化二叉树
 *
 * 算法思想：根据前序遍历规则完成序列化与反序列化。所谓序列化指的是遍历二叉树为字符串；
 *     所谓反序列化指的是依据字符串重新构造成二叉树。
 *     依据前序遍历序列来序列化二叉树，因为前序遍历序列是从根结点开始的。当在遍历二叉树时碰到Null指针时，
 *     这些Null指针被序列化为一个特殊的字符“#”。
 *     另外，结点之间的数值用逗号隔开。
 *
 * @Author Crystal
 * @Date 2019/7/18 22:07
 * @Version 1.0
 **/
public class t_61 {
    /**
     * 定义二叉树
     */
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode parent;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    private static int index = -1;

    public static String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }

    public static TreeNode Deserialize(String str) {
        index ++;
        str = str.replace("{","");
        str = str.replace("}","");

        String[] strs = str.split(",");
        TreeNode node = null;
        if(!"#".equals(strs[index])){
            node = new TreeNode(Integer.valueOf(strs[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
        return node;
    }

    private static void assemble(TreeNode node,
                                 TreeNode left,
                                 TreeNode right,
                                 TreeNode parent) {
        node.left = left;
        node.right = right;
        node.parent = parent;
    }

    public static void main(String[] args) {
        test01();
    }

    //                            1
    //                  2                   3
    //             4         5          6          7
    //          8     9   10   11   12   13    14   15
    public static void test01() {
        TreeNode n1 = new TreeNode(1); // 12
        TreeNode n2 = new TreeNode(2); // 10
        TreeNode n3 = new TreeNode(3); // 14
        TreeNode n4 = new TreeNode(4); // 9
        TreeNode n5 = new TreeNode(5); // 11
        TreeNode n6 = new TreeNode(6); // 13
        TreeNode n7 = new TreeNode(7); // 15
        TreeNode n8 = new TreeNode(8); // 4
        TreeNode n9 = new TreeNode(9); // 2
        TreeNode n10 = new TreeNode(10); // 5
        TreeNode n11 = new TreeNode(11); // 1
        TreeNode n12 = new TreeNode(12); // 6
        TreeNode n13 = new TreeNode(13); // 3
        TreeNode n14 = new TreeNode(14); // 7
        TreeNode n15 = new TreeNode(15); // null

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, n8, n9, n2);
        assemble(n5, n10, n11, n2);
        assemble(n6, n12, n13, n3);
        assemble(n7, n14, n15, n3);
        assemble(n8, null, null, n4);
        assemble(n9, null, null, n4);
        assemble(n10, null, null, n5);
        assemble(n11, null, null, n5);
        assemble(n12, null, null, n6);
        assemble(n13, null, null, n6);
        assemble(n14, null, null, n7);
        assemble(n15, null, null, n7);

        System.out.println(Serialize(n1));
        print(Deserialize("{5,4,#,3,#,2}"));
    }

    //先序遍历二叉树
    private static void print(TreeNode node) {
        if(node!=null){
            System.out.print(node+" ");
        }
        if(node.left != null){
            print(node.left);
        }
        if(node.right != null){
            print(node.right);
        }
    }
}